A variant of the `indexmap` crate that amortizes the cost of resizes.
[`IndexMap`] is a hash table where the iteration order of the key-value
pairs is independent of the hash values of the keys.
[`IndexSet`] is a corresponding hash set using the same implementation and
with similar properties.
[`IndexMap`]: map/struct.IndexMap.html
[`IndexSet`]: set/struct.IndexSet.html
### Amortization
This crate is an ongoing fork of [`indexmap`] that amortizes the cost of resizes.
If you're unsure if you need this, take a look at the documentation of [`griddle`]
and [`atone`], which provide the underlying amortization.
[`indexmap`]: https://github.com/bluss/indexmap/
[`griddle`]: https://github.com/jonhoo/griddle/
[`atone`]: https://github.com/jonhoo/atone/
### Feature Highlights
[`IndexMap`] and [`IndexSet`] are drop-in compatible with the std `HashMap`
and `HashSet`, but they also have some features of note:
- The ordering semantics (see their documentation for details)
- Sorting methods and the [`.pop()`][IndexMap::pop] methods.
- The [`Equivalent`] trait, which offers more flexible equality definitions
between borrowed and owned versions of keys.
- The [`MutableKeys`][map::MutableKeys] trait, which gives opt-in mutable
access to hash map keys.
### Alternate Hashers
[`IndexMap`] and [`IndexSet`] have a default hasher type `S = RandomState`,
just like the standard `HashMap` and `HashSet`, which is resistant to
HashDoS attacks but not the most performant. Type aliases can make it easier
to use alternate hashers:
```
use fnv::FnvBuildHasher;
use fxhash::FxBuildHasher;
use indexmap_amortized::{IndexMap, IndexSet};
type FnvIndexMap = IndexMap;
type FnvIndexSet = IndexSet;
type FxIndexMap = IndexMap;
type FxIndexSet = IndexSet;
let std: IndexSet = (0..100).collect();
let fnv: FnvIndexSet = (0..100).collect();
let fx: FxIndexSet = (0..100).collect();
assert_eq!(std, fnv);
assert_eq!(std, fx);
```
### Rust Version
This version of indexmap requires Rust 1.48 or later.
This version of indexmap requires Rust 1.48+.
The indexmap 1.x release series will use a carefully considered version
upgrade policy, where in a later 1.x version, we will raise the minimum
required Rust version.
## No Standard Library Targets
This crate supports being built without `std`, requiring
`alloc` instead. This is enabled automatically when it is detected that
`std` is not available. There is no crate feature to enable/disable to
trigger this. It can be tested by building for a std-less target.
- Creating maps and sets using [`new`][IndexMap::new] and
[`with_capacity`][IndexMap::with_capacity] is unavailable without `std`.
Use methods [`IndexMap::default`][def],
[`with_hasher`][IndexMap::with_hasher],
[`with_capacity_and_hasher`][IndexMap::with_capacity_and_hasher] instead.
A no-std compatible hasher will be needed as well, for example
from the crate `twox-hash`.
- Macros [`indexmap!`] and [`indexset!`] are unavailable without `std`.
[def]: map/struct.IndexMap.html#impl-Default